import java.util.*;

public class Main {
    public static int[] createArray1(int k){
        int[] arr = new int[k];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(100);
        }
        return arr;
    }
    public static void main(String[] args) {
        int[] array = createArray1(10);
        Sort.partitionHoare(array,0,array.length-1);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }

    public static void main2(String[] args) {
        // Java中: PriorityQueue默认是 小根堆 容量是 11
        // 放的一定是可比较大小的元素,常用 "比较器"
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(1);
        priorityQueue.offer(2);
        priorityQueue.offer(3);
        priorityQueue.offer(4);
        priorityQueue.offer(5);
        System.out.println(priorityQueue.peek());

    }

    public static void main3(String[] args) {
        PriorityQueue<String> priorityQueue = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.length()-o2.length();
            }
        });
        PriorityQueue<String> priorityQueue1 = new PriorityQueue<>((o1,o2)->{return o1.length()-o2.length();});
        PriorityQueue<String> priorityQueue2 = new PriorityQueue<>((o1,o2)->o1.length()-o2.length());
    }

    public static void main4(String[] args) {
        int[] array = {48,15,3,95,25,63,47,201,128,360};
        topK(array,5);
        topK2(array,5);
        Heap heap = new Heap();
        heap.initArray(array);
        heap.disPlay();
        heap.createHeap();
        heap.disPlay();
        heap.heapSort();
        heap.disPlay();
    }

    /**
     * topK :
     *   1.求前K个最大(小)的
     *   2.求第K大(小)的
     * @param array
     * @param k
     */
    public static void topK(int[] array, int k){
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

        for (int i = 0; i < array.length; i++) {
            priorityQueue.offer(array[i]);
        }
        for (int i = 0; i < k; i++) {
            System.out.print(priorityQueue.poll() + " ");
        }
        System.out.println();
    }

    /**
     * 优化后的topK函数
     * 如果求前K个最大(小)的 建大小为K的小(大)根堆
     *  时间复杂度 Nlngk
     * @param array
     * @param k
     */
    public static void topK2(int[] array,int k){
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
        for (int i = 0; i < array.length; i++) {
            if (i < k){
                priorityQueue.offer(array[i]);
            }else {
                int top = priorityQueue.peek();
                if (array[i] > priorityQueue.peek()){
                    priorityQueue.poll();
                    priorityQueue.offer(array[i]);
                }
            }

        }

        for (int i = 0; i < k; i++) {
            System.out.print(priorityQueue.poll() + " ");
        }
        System.out.println();
    }
}
